package cn.xiaolang.function.data_structure;

/**
 * 二进制求和
 * <p>
 * 给你两个二进制字符串，返回它们的和（用二进制表示）。
 * 输入为 非空 字符串且只包含数字 1 和 0。
 * </p>
 *
 * @author fuhw/Dean
 * @date 2020-04-09
 */
public class StringBinaryOperator {

    public static void main(String[] args) {
        System.out.println(addBinary("1010", "1011"));
    }

    /**
     * 思路：
     * 1 获取两个字符串的最大长度
     * 2 短字符串补0
     * 3 char字符-'0'做二进制运算，>=2进位，最后一个字符进位补充1
     *
     * @param a
     * @param b
     * @return
     */
    private static String addBinary(String a, String b) {

        char zeroChar = '0';
        int aLength = a.length();
        int bLength = b.length();
        int maxLength = aLength > bLength ? aLength : bLength;

        // 补位
        if (aLength > bLength) {
            for (int i = 0; i < aLength - bLength; i++) {
                b = zeroChar + b;
            }
        } else {
            for (int i = 0; i < bLength - aLength; i++) {
                a = zeroChar + a;
            }
        }
        StringBuilder result = new StringBuilder();
        // 是否要进位
        boolean carry = false;
        for (int i = maxLength - 1; i >= 0; i--) {
            int bitPlus = carry ? (a.charAt(i) - zeroChar + b.charAt(i) - zeroChar + 1)
                    : (a.charAt(i) - zeroChar + b.charAt(i) - zeroChar);
            if (bitPlus >= 2) {
                result.append(bitPlus - 2);
                carry = true;
            } else {
                result.append(bitPlus);
                carry = false;
            }
        }
        if (carry) {
            result.append('1');
        }

        return result.reverse().toString();
    }
}
